#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

//Definition for a binary tree node.
struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr)
	{
	}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr)
	{
	}
	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right)
	{
	}
};

class Solution {
        tuple<int, int, int, int, int> get_max_sum(TreeNode *root){
                if(!root){
                        return {0, 0, 1, INT32_MIN, INT32_MAX };
                }
                auto [sumr, maxsumr, isbstr, maxvr, minvr] = get_max_sum(root->right);
                auto [suml, maxsuml, isbstl, maxvl, minvl] = get_max_sum(root->left);

                int maxv = max({maxvr, maxvl, root->val});
                int minv = min({minvr, minvl, root->val});
                int maxsum = max(maxsumr, maxsuml);
                int sum = root->val + sumr + suml;
                int isbst = isbstl && isbstr && root->val > maxvl && root->val < minvr; 
                if(isbst){
                        maxsum = max(maxsum, sum);
                }
                return {sum, maxsum, isbst, maxv, minv};
        }
    public:
	int maxSumBST(TreeNode *root)
	{
                auto [sum, maxsum, isbst, maxv, minv] = get_max_sum(root);
                return maxsum;
	}
};

int main()
{

}